'''
@Descripttion: 
@version: 
@encoding: utf-8
@Author: qiurongcan
Date: 2025-10-13 17:53:53
LastEditTime: 2025-10-13 18:15:41
'''

from collections import defaultdict, deque


class Solution:
    def canFinish(self, numCourses, prerequisites):

        # 每一门课程的入度：就是修这门课程时，需要先修几门课程
        indegree = [0] * numCourses
        adj = defaultdict(list)

        for cur, pre in prerequisites:
            indegree[cur] += 1 # 这门课程的入度
            adj[pre].append(cur) # 这门课程修完，可以修哪些课程

        q = deque()
        for i in range(numCourses):
            if indegree[i] == 0:
                q.append(i)
        
        while q:
            n = len(q)
            for i in range(n):
                pre = q.popleft()
                numCourses -= 1

                for cur in adj[pre]:
                    indegree[cur] -= 1

                    if indegree[cur] == 0:
                        q.append(cur)
            
        return numCourses == 0



